

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

class InsertSort{
    public static void main(String args[]){
        int arr[]={Integer.MIN_VALUE,2,4,5,7,1,2,3,6};
        insertion_sort(arr);
     
    }

    private static void insertion_sort(int[] arr) {
        for(int j=2;j<arr.length;j++){
            int key=arr[j];
            int i=j-1;
            for(;i>0&&arr[i]>key;i--){
                arr[i+1]=arr[i];
            }
            arr[i+1]=key;
            System.out.println(Arrays.toString(arr));
        }
        //System.out.println(Arrays.toString(arr));
    }
    private static void insertion_sort2(int[] arr) {
        for(int j=2;j<arr.length;j++){
            int key=arr[j];
            int i=j-1;
            for(;i>0&&arr[i]<key;i--){//
                arr[i+1]=arr[i];
            }
            arr[i+1]=key;
            System.out.println(Arrays.toString(arr));
        }
        //System.out.println(Arrays.toString(arr));
    }

}